package com.merit;


import java.util.*;

/**
 * @author xingdongyang
 * @date 2020/6/1
 */
public class RemoveDuplicates {
    public static void main(String[] args) {
        //removeDuplicates(new int[]{0, 0, 1, 1, 1, 2, 2, 3, 3, 4});
        //System.out.println(strStr("a", ""));
        //System.out.println(divide(10, 3));
        System.out.println(findSubstring("barfoothefoobarman",new String[]{"foo","bar"}).toString());
    }

    /**
     * 给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
     * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
     */
    public static int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int tmp = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[tmp] != nums[i]) {
                tmp++;
                nums[tmp] = nums[i];
            }
        }
        return tmp + 1;
    }

    /**
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
     * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
     * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素
     */
    public static int removeElement(int[] nums, int val) {
        if (nums.length == 0) {
            return 0;
        }
        int tmp = 0;
        for (int i = 0; i < nums.length; i++) {
            if (val != nums[i]) {
                nums[tmp] = nums[i];
                tmp++;
            }
        }
        return tmp;
    }

    /**
     * 实现 strStr() 函数。
     * 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
     */
    public static int strStr(String haystack, String needle) {
        if (Objects.isNull(needle) || Objects.isNull(haystack) || (needle.length() == 0 && haystack.length() == 0)) {
            return 0;
        }
        if (needle.length() > haystack.length()) {
            return -1;
        }
        int flag = -1;
        for (int i = 0; i < haystack.length(); i++) {
            if (needle.startsWith(haystack.charAt(i) + "")) {
                if (needle.length() + i > haystack.length()) {
                    return -1;
                }
                if (needle.equals(haystack.substring(i, i + needle.length()))) {
                    flag = i;
                }
            }
        }
        return flag;
    }

    /**
     * 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
     * 返回被除数 dividend 除以除数 divisor 得到的商。
     * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
     */
    public static int divide(int dividend, int divisor) {
        boolean sign = (dividend > 0) ^ (divisor > 0);
        int result = 0;
        if (dividend > 0) {
            dividend = -dividend;
        }
        if (divisor > 0) {
            divisor = -divisor;
        }
        while (dividend <= divisor) {
            int tempResult = -1;
            int tempDivisor = divisor;
            while (dividend <= (tempDivisor << 1)) {
                if (tempDivisor <= (Integer.MIN_VALUE >> 1)) {
                    break;
                }
                tempResult = tempResult << 1;
                tempDivisor = tempDivisor << 1;
            }
            dividend = dividend - tempDivisor;
            result += tempResult;
        }
        if (!sign) {
            if (result <= Integer.MIN_VALUE) {
                return Integer.MAX_VALUE;
            }
            result = -result;
        }
        return result;
    }

    /**
     * 给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
     * 注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
     * 不存在返回[]
     * @see  https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/
     * */
    public static List<Integer> findSubstring(String s, String[] words) {
        if(Objects.isNull(s)) {
            return new ArrayList<>();
        }
        // 获取所有words 拼接无重复字符串
        List<String> wordList = new ArrayList<>();
        recursionArrange(words, 0, words.length,wordList);
        System.out.println(wordList.toString());
        return null;
    }

    /**
     * 全排序
     * */
    public static void recursionArrange(String[] arrayA, int start, int end, List<String> result) {
        if (end <= 1) {
            return;
        }
        if (start == end -1) {
            result.addAll(Arrays.asList(arrayA));
        } else {
            for (int i = start; i < end; i++) {
                swap(arrayA, i, start);
                recursionArrange(arrayA, start + 1, end, result);
                swap(arrayA, i, start);
            }
        }
    }

    /**
     * 交换数组m位置和n位置上的值
     */
    private static void swap(String[] arrayA, int m, int n) {
        String temp = arrayA[m];
        arrayA[m] = arrayA[n];
        arrayA[n] = temp;
    }

}
